package myList_1009;

/**
 * 顺序表：物理上元素相连的线性表
 * 约束：
 * 1) 0 <= size <= array.length
 * array[0, size) != null
 * array[size, array.length) == null
 */
public class MyArrayList implements MyList {
    // 定义属性
    private Long[] array;   // array.length 也就是我们的容量（capacity）
    private int size;       // 保存元素的个数

    // 构造方法
    public MyArrayList() {
        // 容量没有规定，自行定义为 16 个
        this.array = new Long[16];
        // 这一步不是必须的，把数组中的每个位置都初始化成 null
        for (int i = 0; i < array.length; i++) {
            array[i] = null;
        }
        // 元素个数 = 0
        this.size = 0;
    }

    public MyArrayList(int initialCapacity) {
        this.array = new Long[initialCapacity];
        // 这一步不是必须的，把数组中的每个位置都初始化成 null
        for (int i = 0; i < array.length; i++) {
            array[i] = null;
        }
        // 元素个数 = 0
        this.size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    // 扩容过程仅仅为了内部准备，不会对外
    // O(n)
    private void ensureCapacity() {
        if (this.size < this.array.length) {
            return;     // 此时不需要扩容
        }

        // 需要扩容
        // 1) 申请新数组，容量是原来的 2 倍
        int newLength = this.array.length * 2;
        Long[] newArray = new Long[newLength];

        // 2) 搬家
        for (int i = 0; i < this.size; i++) {
            newArray[i] = this.array[i];
        }

        // 3) 让顺序表的 array 引用指向新数组
        this.array = newArray;
    }

    // 时间复杂度：数据规模是 size，时间复杂度是 O(1)
    // 最坏情况，发生扩容的情况： O(n)
    // 我们认为扩容的发生是小概率事件
    // 平均事件复杂度：O(1)
    @Override
    public boolean add(Long e) {
        ensureCapacity();   // 这个方法结束之后，至少还有一个空间可以插入

        // 为 size 赋予一个新的逻辑含义 —— 尾插时的元素的位置
        array[size] = e;
        // 让元素个数的记录 + 1
        size = size + 1;

        // 返回 true 表示插入成功
        return true;
    }

    // 时间复杂度：O(n)
    @Override
    public void add(int index, Long e) {
        ensureCapacity();   // 这个方法结束之后，至少还有一个空间可以插入

        if (index < 0 || index > size) {
            // 下标不合法
            throw new ArrayIndexOutOfBoundsException("下标不合法");
        }

        // 此时下标一定是合法的
        // 将每个结点往后移位
        // i: 移位时的出发点
        for (int i = size - 1; i >= index; i--) {
            // array[i] 的元素搬到  array[i + 1]
            array[i + 1] = array[i];
        }

        // 将 e 放到 index 位置
        array[index] = e;

        // 元素个数增加了 1
        size = size + 1;
    }

    // 时间复杂度: O(n)
    @Override
    public Long remove(int index) {
        // 下标合法性检查
        if (index < 0 || index >= size) {
            // 下标不合法
            throw new ArrayIndexOutOfBoundsException("下标不合法");
        }

        // 先把要删除的元素保存起来
        Long e = array[index];

        // i 代表搬元素时的起始位置 [index + 1, size)
        for (int i = index + 1; i < size; i++) {
            array[i - 1] = array[i];
        }

        // 把不存在的元素置为 null
        // 真实中是否要置 null，需要根据性能考虑
        array[size - 1] = null;

        // 元素个数减一
        size = size - 1;

        // 返回被删除的元素
        return e;
    }

    // 时间复杂度是 O(n)
    @Override
    public boolean remove(Long e) {
        // 按照从前到后的顺序，找到第一个遇到的 e
        for (int i = 0; i < size; i++) {
            // 毕竟 array 的值 是否 和 e 相等（equals）
            if (array[i].equals(e)) {
                // 删除 [i] 位置的元素
                remove(i);  // O(n)
                return true;
            }
        }

        // 说明没有找到 e
        return false;
    }

    // O(1)
    @Override
    public Long get(int index) {// 下标合法性检查
        if (index < 0 || index >= size) {
            // 下标不合法
            throw new ArrayIndexOutOfBoundsException("下标不合法");
        }

        return array[index];
    }

    // O(1)
    @Override
    public Long set(int index, Long e) {
        // 下标合法性检查
        if (index < 0 || index >= size) {
            // 下标不合法
            throw new ArrayIndexOutOfBoundsException("下标不合法");
        }

        Long oldE = array[index];

        array[index] = e;

        return oldE;
    }


    // O(n)
    @Override
    public int indexOf(Long e) {
        for (int i = 0; i < size; i++) {
            if (array[i].equals(e)) {
                return i;
            }
        }

        return -1;
    }

    // O(n)
    @Override
    public int lastIndexOf(Long e) {
        for (int i = size - 1; i >= 0; i--) {
            if (array[i].equals(e)) {
                return i;
            }
        }

        return -1;
    }

    // O(n)
    @Override
    public boolean contains(Long e) {
        return indexOf(e) != -1;
    }

    @Override
    public void clear() {
        // array 中全部置为 null
        for (int i = 0; i < size; i++) {
            array[i] = null;
        }
        this.size = 0;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private static void 检查顺序表是否合法(MyArrayList list) {
        // 0 <= size <= array.length
        if (list.size < 0) {
            throw new RuntimeException();
        }

        if (list.size > list.array.length) {
            throw new RuntimeException();
        }
        // array[0, size) != null
        for (int i = 0; i < list.size; i++) {
            if (list.array[i] == null) {
                throw new RuntimeException();
            }
        }
        // array[size, array.length) == null
        for (int i = list.size; i < list.array.length; i++) {
            if (list.array[i] != null) {
                throw new RuntimeException();
            }
        }
    }

    private static void 断言顺序表的元素个数一定是(MyArrayList list, int size) {
        if (list.size != size) {
            throw new RuntimeException();
        }
    }

    private static void 断言顺序表的指定位置元素一定是(MyArrayList list, int index, long e) {
        // Long != long
        // long != long
        if (list.array[index] != e) {
            throw new RuntimeException();
        }
    }
    public static void main(String[] args) {
        // 之所以把测试代码写这里，是方便读取 private 的属性
        MyArrayList list = new MyArrayList();
        检查顺序表是否合法(list);

        // 无参构造方法定义的顺序表，size 应该是 0
        断言顺序表的元素个数一定是(list, 0);

        // 先测试尾插 add()
        boolean r;

        r = list.add(Long.valueOf(100));    // 手动把 int 包装成 Long
        // 检查 r 必须是 true
        if (r == false) {
            throw new RuntimeException();
        }

        检查顺序表是否合法(list);
        断言顺序表的元素个数一定是(list, 1);
        断言顺序表的指定位置元素一定是(list, 0, 100);

        r = list.add(200L);         // 编译器自动把 long 包装成 Long
        if (r == false) {
            throw new RuntimeException();
        }
        检查顺序表是否合法(list);
        断言顺序表的元素个数一定是(list, 2);
        断言顺序表的指定位置元素一定是(list, 0, 100);
        断言顺序表的指定位置元素一定是(list, 1, 200);

        r = list.add(300L);
        if (r == false) {
            throw new RuntimeException();
        }
        检查顺序表是否合法(list);
        断言顺序表的元素个数一定是(list, 3);
        断言顺序表的指定位置元素一定是(list, 0, 100);
        断言顺序表的指定位置元素一定是(list, 1, 200);
        断言顺序表的指定位置元素一定是(list, 2, 300);

        // 测试 根据 index 进行插入 add(int index, Long e)

        // [100, 200, 300]
        list.add(3, 1000L);
        // [100, 200, 300, 1000]
        检查顺序表是否合法(list);
        断言顺序表的元素个数一定是(list, 4);
        断言顺序表的指定位置元素一定是(list, 0, 100);
        断言顺序表的指定位置元素一定是(list, 1, 200);
        断言顺序表的指定位置元素一定是(list, 2, 300);
        断言顺序表的指定位置元素一定是(list, 3, 1000);

        // [100, 200, 300, 1000]
        list.add(0, 2000L);
        // [2000, 100, 200, 300, 1000]
        检查顺序表是否合法(list);
        断言顺序表的元素个数一定是(list, 5);
        断言顺序表的指定位置元素一定是(list, 0, 2000);
        断言顺序表的指定位置元素一定是(list, 1, 100);
        断言顺序表的指定位置元素一定是(list, 2, 200);
        断言顺序表的指定位置元素一定是(list, 3, 300);
        断言顺序表的指定位置元素一定是(list, 4, 1000);

        // [2000, 100, 200, 300, 1000]
        list.add(2, 3000L);
        // [2000, 100, 3000, 200, 300, 1000]
        检查顺序表是否合法(list);
        断言顺序表的元素个数一定是(list, 6);
        断言顺序表的指定位置元素一定是(list, 0, 2000);
        断言顺序表的指定位置元素一定是(list, 1, 100);
        断言顺序表的指定位置元素一定是(list, 2, 3000);
        断言顺序表的指定位置元素一定是(list, 3, 200);
        断言顺序表的指定位置元素一定是(list, 4, 300);
        断言顺序表的指定位置元素一定是(list, 5, 1000);

        // [2000, 100, 3000, 200, 300, 1000]
        //        list.add(13, 4000L);
        // 非法下标，应该看到 下标越界异常

        // [2000, 100, 3000, 200, 300, 1000]
        Long e = list.remove(2);
        // [2000, 100, 200, 300, 1000]
        if (e != 3000) {
            throw new RuntimeException();
        }
        检查顺序表是否合法(list);
        断言顺序表的元素个数一定是(list, 5);
        断言顺序表的指定位置元素一定是(list, 0, 2000);
        断言顺序表的指定位置元素一定是(list, 1, 100);
        断言顺序表的指定位置元素一定是(list, 2, 200);
        断言顺序表的指定位置元素一定是(list, 3, 300);
        断言顺序表的指定位置元素一定是(list, 4, 1000);

        // 测试下删除 remove(0)  remove(size - 1)
        //[100,200,300,1000]
//        list.remove(0);
//        检查顺序表是否合法(list);
//        断言顺序表的元素个数一定是(list,4);
//        断言顺序表的指定位置元素一定是(list,0,100);
//        断言顺序表的指定位置元素一定是(list,1,200);
//        断言顺序表的指定位置元素一定是(list,2,300);
//        断言顺序表的指定位置元素一定是(list,3,1000);

        // 测试下删除 remove(0)  remove(size - 1)
        //[100,200,300]
//        list.remove(3);
//        检查顺序表是否合法(list);
//        断言顺序表的元素个数一定是(list,3);
//        断言顺序表的指定位置元素一定是(list,0,100);
//        断言顺序表的指定位置元素一定是(list,1,200);
//        断言顺序表的指定位置元素一定是(list,2,300);

        // [2000, 100, 200, 300, 1000]
        r = list.remove(100L);
        // [2000, 200, 300, 1000]
        if (r == false) {
            throw new RuntimeException();
        }

        检查顺序表是否合法(list);
        断言顺序表的元素个数一定是(list, 4);
        断言顺序表的指定位置元素一定是(list, 0, 2000);
        断言顺序表的指定位置元素一定是(list, 1, 200);
        断言顺序表的指定位置元素一定是(list, 2, 300);
        断言顺序表的指定位置元素一定是(list, 3, 1000);


        // [2000, 200, 300, 1000]
        list.add(200L);
        list.add(200L);
        // [2000, 200, 300, 1000, 200, 200]
        r = list.remove(200L);
        // [2000, 300, 1000, 200, 200]
        if (r == false) {
            throw new RuntimeException();
        }

        检查顺序表是否合法(list);
        断言顺序表的元素个数一定是(list, 5);
        断言顺序表的指定位置元素一定是(list, 0, 2000);
        断言顺序表的指定位置元素一定是(list, 1, 300);
        断言顺序表的指定位置元素一定是(list, 2, 1000);
        断言顺序表的指定位置元素一定是(list, 3, 200);
        断言顺序表的指定位置元素一定是(list, 4, 200);

        // 测试如果没有元素 r = remove(5000L);
        r=list.remove(5000L);
        if (r == true) {
            throw new RuntimeException();
        }
    }
}
